package com.monotoneStack;

import java.util.Stack;

/**
 * 柱状图中最大的矩形
 */
public class LargestRectangleinHistogram0122_84 {
    public int largestRectangleArea(int[] heights) {
        // 数组扩容，在头和尾各加入一个元素
        int [] newHeights = new int[heights.length + 2];
        for (int index = 0; index < heights.length; index++){
            newHeights[index + 1] = heights[index];
        }
        heights = newHeights;

        //单调栈思路
        //找到左右方向第一个矮的柱子，差值为宽
        Stack<Integer> stack = new Stack<>();
        stack.push(0);

        int res = 0;
        for (int i = 1; i < heights.length; i++) {
            if(heights[i] >= heights[stack.peek()]){
                stack.push(i);
            }else {
                while (!stack.isEmpty() && heights[i] < heights[stack.peek()]){
                    int mid = stack.pop();
                    int right = i;
                    if(!stack.isEmpty()) {
                        int left = stack.peek();
                        int count = (right - left - 1) * heights[mid];
                        res = Math.max(res, count);
                    }
                }
                stack.push(i);
            }
        }
        return res;
    }
}
